const std = @import("std");
const Point = @import("../point.zig");

/// A convex hull.
pub const Hull = @This();

/// The final points of the hull
points: []Point,

allocator: std.mem.Allocator,

/// Use Andrew algorithm to compute the convex hull of a set of points.
pub fn init(points: *const std.ArrayList(Point), allocator: std.mem.Allocator) *Hull {
    const count: usize = points.items.len;

    const sorted_points = allocator.alloc(Point, count) catch @panic("Out of memory");
    defer allocator.free(sorted_points);

    std.mem.copyForwards(Point, sorted_points, points.items);
    std.mem.sort(Point, sorted_points, {}, comparePoint);

    var vertices = allocator.alloc(Point, count) catch @panic("Out of memory");
    defer allocator.free(vertices);

    var idx_taken = allocator.alloc(bool, count) catch @panic("Out of memory");
    defer allocator.free(idx_taken);

    vertices[0] = sorted_points[0];
    idx_taken[0] = true;
    vertices[1] = sorted_points[1];
    idx_taken[1] = true;
    var top_idx: usize = 1;
    var idx_taken_idx: usize = 1;
    for (2..count) |i| {
        const p = sorted_points[i];
        while (true) {
            if (top_idx > 0) {
                const cross_product = cross(&vertices[top_idx - 1], &vertices[top_idx], &p);
                if (cross_product < 0) {
                    top_idx -= 1;

                    idx_taken[idx_taken_idx] = false;
                    idx_taken_idx -= 1;
                } else if (cross_product == 0) {
                    top_idx -= 1;

                    idx_taken_idx -= 1;
                } else {
                    break;
                }
            } else {
                break;
            }
        }

        top_idx += 1;
        vertices[top_idx] = p;

        idx_taken[i] = true;
        idx_taken_idx = i;
    }

    const lower_top = top_idx;
    for (1..count) |i| {
        const idx = count - i - 1;
        const p = sorted_points[idx];
        if (idx_taken[idx] and 0 != idx) {
            continue;
        }

        while (top_idx > lower_top and cross(&vertices[top_idx - 1], &vertices[top_idx], &p) <= 0) {
            top_idx -= 1;
        }

        if (0 != idx) {
            top_idx += 1;
            vertices[top_idx] = p;
        }
    }

    for (0..count) |i| {
        idx_taken[i] = false;
    }
    const eps = std.math.floatEps(f32);
    const eps_sqr = eps * eps;
    var count_taken: usize = 0;
    for (1..top_idx + 1) |i| {
        if (vertices[i].distanceSquaredTo(&vertices[i - 1]) <= eps_sqr) {
            idx_taken[i] = true;
            count_taken += 1;
        }
    }
    if (vertices[0].distanceSquaredTo(&vertices[top_idx]) <= eps_sqr) {
        idx_taken[top_idx] = true;
        count_taken += 1;
    }

    var hull = allocator.create(Hull) catch @panic("Out of memory");
    hull.allocator = allocator;
    hull.points = allocator.alloc(Point, top_idx + 1 - count_taken) catch @panic("Out of memory");
    var idx: usize = 0;
    for (0..top_idx + 1) |i| {
        if (!idx_taken[i]) {
            hull.points[idx] = vertices[i];
            idx += 1;
        }
    }

    return hull;
}

pub fn deinit(self: *Hull) void {
    self.allocator.free(self.points);

    self.allocator.destroy(self);
}

fn comparePoint(context: void, a: Point, b: Point) bool {
    _ = context;
    if (a.x == b.x) {
        return a.y < b.y;
    } else {
        return a.x < b.x;
    }
}

fn cross(prev_point: *const Point, top_point: *const Point, new_point: *const Point) f32 {
    return (top_point.x - prev_point.x) * (new_point.y - prev_point.y) - (top_point.y - prev_point.y) * (new_point.x - prev_point.x);
}
